Beaconing-Aware Optimal Policies for Two-Hop Routing in Multi-Class Delay Tolerant Networks

摘要

In Delay Tolerant Networks (DTNs), two-hop routing compromises energy versusdelay more conveniently than epidemic routing. Literature providescomprehensive results on optimal routing policies for mobile nodes withhomogeneous mobility, often neglecting signaling costs. Routing policies arecustomarily computed by means of fluid approximation techniques, which assuresolutions to be optimal only when the number of nodes is infinite, while theyprovide a coarse approximation otherwise. This work addresses heterogeneousmobility patterns and multiple wireless transmission technologies; moreover, weexplicitly consider the beaconing/signaling costs to support routing and thepossibility for nodes to discard packets after a local time. We theoreticallycharacterize the optimal policies by deriving their formal properties. Suchanalysis is leveraged to define two algorithmic approaches which allow to tradeoff optimality with computational efficiency. Theoretical bounds on theapproximation guarantees of the proposed algorithms are derived. We thenexperimentally evaluated them in realistic scenarios of multi-class DTNs.